/*
 * @(#)IdempotentSequence.java   0.3-3 06/05/2001
 *
 *  This file is part of the HTTPClient package
 *  Copyright (C) 1996-2001 Ronald Tschal�r
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free
 *  Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
 *  MA 02111-1307, USA
 *
 *  For questions, suggestions, bug-reports, enhancement-requests etc.
 *  I may be contacted at:
 *
 *  ronald@innovation.ch
 *
 *  The HTTPClient's home page is located at:
 *
 *  http://www.innovation.ch/java/HTTPClient/ 
 *
 */

package org.everrest.http.client;

import java.util.Enumeration;
import java.util.Hashtable;

/**
 * <p/>
 * This class checks whether a sequence of requests is idempotent. This is used
 * to determine which requests may be automatically retried. This class also
 * serves as a central place to record which methods have side effects and which
 * methods are idempotent.
 * <p/>
 * Note: unknown methods (i.e. a method which is not HEAD, GET, POST, PUT,
 * DELETE, OPTIONS, TRACE, PROPFIND, PROPPATCH, MKCOL, COPY, MOVE, LOCK, or
 * UNLOCK) are treated conservatively, meaning they are assumed to have side
 * effects and are not idempotent.
 * <p/>
 * Usage:
 * <p/>
 * <PRE>
 * IdempotentSequence seq = new IdempotentSequence();
 * seq.add(r1);
 * ...
 * if (seq.isIdempotent(r1)) ...
 * ...
 * </PRE>
 *
 * @author Ronald Tschal�r
 * @version 0.3-3 06/05/2001
 */
class IdempotentSequence {
    /** method number definitions */
    private static final int UNKNOWN = 0, HEAD = 1, GET = 2, POST = 3, PUT = 4, DELETE = 5, OPTIONS = 6, TRACE = 7,

    // DAV methods
    PROPFIND = 8, PROPPATCH = 9, MKCOL = 10, COPY = 11, MOVE = 12, LOCK = 13, UNLOCK = 14;

    /** these are the history of previous requests */
    private int[] m_history;

    private String[] r_history;

    private int m_len, r_len;

    /** trigger analysis of threads */
    private boolean analysis_done = false;

    private Hashtable threads = new Hashtable();

    // Constructors

    /** Start a new sequence of requests. */
    public IdempotentSequence() {
        m_history = new int[10];
        r_history = new String[10];
        m_len = 0;
        r_len = 0;
    }

    // Methods

    /**
     * Add the request to the end of the list of requests. This is used to build
     * the complete sequence of requests before determining whether the sequence
     * is idempotent.
     *
     * @param req
     *         the next request
     */
    public void add(Request req) {
        if (m_len >= m_history.length)
            m_history = Util.resizeArray(m_history, m_history.length + 10);
        m_history[m_len++] = methodNum(req.getMethod());

        if (r_len >= r_history.length)
            r_history = Util.resizeArray(r_history, r_history.length + 10);
        r_history[r_len++] = req.getRequestURI();
    }

    /**
     * Is this request part of an idempotent sequence? This method <em>must
     * not</em> be called before all requests have been added to this sequence;
     * similarly, <var>add()</var> <em>must not</em> be called after this method
     * was invoked.
     * <p/>
     * We split up the sequence of requests into individual sub-sequences, or
     * threads, with all requests in a thread having the same request-URI and no
     * two threads having the same request-URI. Each thread is then marked as
     * idempotent or not according to the following rules:
     * <OL>
     * <LI>If any method is UNKNOWN then the thread is not idempotent;
     * <LI>else, if no method has side effects then the thread is idempotent;
     * <LI>else, if the first method has side effects and is complete then the
     * thread is idempotent;
     * <LI>else, if the first method has side effects, is not complete, and no
     * other method has side effects then the thread is idempotent;
     * <LI>else the thread is not idempotent.
     * </OL>
     * <p/>
     * The major assumption here is that the side effects of any method only
     * apply to resource specified. E.g. a <tt>"PUT /barbara.html"</tt> will only
     * affect the resource "/barbara.html" and nothing else. This assumption is
     * violated by POST of course; however, POSTs are not pipelined and will
     * therefore never show up here.
     *
     * @param req
     *         the request
     */
    public boolean isIdempotent(Request req) {
        if (!analysis_done)
            do_analysis();

        return ((Boolean)threads.get(req.getRequestURI())).booleanValue();
    }

    private static final Object INDET = new Object();

    private void do_analysis() {
        for (int idx = 0; idx < r_len; idx++) {
            Object t_state = threads.get(r_history[idx]);

            if (m_history[idx] == UNKNOWN)
                threads.put(r_history[idx], Boolean.FALSE);
            else if (t_state == null) // new thread
            {
                if (methodHasSideEffects(m_history[idx])) {
                    if (methodIsComplete(m_history[idx])) // is idempotent
                        threads.put(r_history[idx], Boolean.TRUE);
                    else
                        threads.put(r_history[idx], Boolean.FALSE);
                } else
                    // indeterminate
                    threads.put(r_history[idx], INDET);
            } else
            // update thread
            {
                if (t_state == INDET && methodHasSideEffects(m_history[idx]))
                    threads.put(r_history[idx], Boolean.FALSE);
            }
        }

        // any thread still indeterminate must be idempotent
        Enumeration te = threads.keys();
        while (te.hasMoreElements()) {
            String res = (String)te.nextElement();
            if (threads.get(res) == INDET)
                threads.put(res, Boolean.TRUE);
        }
    }

    /**
     * A method is idempotent if the side effects of N identical requests is the
     * same as for a single request (Section 9.1.2 of RFC-????).
     *
     * @return true if method is idempotent
     */
    public static boolean methodIsIdempotent(String method) {
        return methodIsIdempotent(methodNum(method));
    }

    private static boolean methodIsIdempotent(int method) {
        switch (method) {
            case HEAD:
            case GET:
            case PUT:
            case DELETE:
            case OPTIONS:
            case TRACE:
            case PROPFIND:
            case PROPPATCH:
            case COPY:
            case MOVE:
                return true;
            case UNKNOWN:
            case POST:
            case MKCOL:
            case LOCK:
            case UNLOCK:
            default:
                return false;
        }
    }

    /**
     * A method is complete if any side effects of the request affect the
     * complete resource. For example, a PUT is complete but a PUT with
     * byte-ranges wouldn't be. In essence, if a request uses a method which has
     * side effects and is complete then the state of the resource after the
     * request is independent of the state of the resource before the request.
     *
     * @return true if method is complete
     */
    public static boolean methodIsComplete(String method) {
        return methodIsComplete(methodNum(method));
    }

    private static boolean methodIsComplete(int method) {
        switch (method) {
            case HEAD:
            case GET:
            case PUT:
            case DELETE:
            case OPTIONS:
            case TRACE:
            case PROPFIND:
            case COPY:
            case MOVE:
            case LOCK:
            case UNLOCK:
                return true;
            case UNKNOWN:
            case POST:
            case PROPPATCH:
            case MKCOL:
            default:
                return false;
        }
    }

    public static boolean methodHasSideEffects(String method) {
        return methodHasSideEffects(methodNum(method));
    }

    private static boolean methodHasSideEffects(int method) {
        switch (method) {
            case HEAD:
            case GET:
            case OPTIONS:
            case TRACE:
            case PROPFIND:
            case LOCK:
            case UNLOCK:
                return false;
            case UNKNOWN:
            case POST:
            case PUT:
            case DELETE:
            case PROPPATCH:
            case MKCOL:
            case COPY:
            case MOVE:
            default:
                return true;
        }
    }

    private static int methodNum(String method) {
        if (method.equals("GET"))
            return GET;
        if (method.equals("POST"))
            return POST;
        if (method.equals("HEAD"))
            return HEAD;
        if (method.equals("PUT"))
            return PUT;
        if (method.equals("DELETE"))
            return DELETE;
        if (method.equals("OPTIONS"))
            return OPTIONS;
        if (method.equals("TRACE"))
            return TRACE;
        if (method.equals("PROPFIND"))
            return PROPFIND;
        if (method.equals("PROPPATCH"))
            return PROPPATCH;
        if (method.equals("MKCOL"))
            return MKCOL;
        if (method.equals("COPY"))
            return COPY;
        if (method.equals("MOVE"))
            return MOVE;
        if (method.equals("LOCK"))
            return LOCK;
        if (method.equals("UNLOCK"))
            return UNLOCK;

        return UNKNOWN;
    }

/*
   public static void main(String args[])
   {
      IdempotentSequence seq = new IdempotentSequence();

      seq.add(new Request(null, "GET", "/b1", null, null, null, false));
      seq.add(new Request(null, "PUT", "/b2", null, null, null, false));
      seq.add(new Request(null, "GET", "/b1", null, null, null, false));
      seq.add(new Request(null, "PUT", "/b3", null, null, null, false));
      seq.add(new Request(null, "GET", "/b2", null, null, null, false));
      seq.add(new Request(null, "POST", "/b8", null, null, null, false));
      seq.add(new Request(null, "PUT", "/b3", null, null, null, false));
      seq.add(new Request(null, "GET", "/b1", null, null, null, false));
      seq.add(new Request(null, "TRACE", "/b4", null, null, null, false));
      seq.add(new Request(null, "GET", "/b9", null, null, null, false));
      seq.add(new Request(null, "LINK", "/b4", null, null, null, false));
      seq.add(new Request(null, "GET", "/b4", null, null, null, false));
      seq.add(new Request(null, "PUT", "/b5", null, null, null, false));
      seq.add(new Request(null, "HEAD", "/b5", null, null, null, false));
      seq.add(new Request(null, "PUT", "/b5", null, null, null, false));
      seq.add(new Request(null, "POST", "/b9", null, null, null, false));
      seq.add(new Request(null, "GET", "/b6", null, null, null, false));
      seq.add(new Request(null, "DELETE", "/b6", null, null, null, false));
      seq.add(new Request(null, "HEAD", "/b6", null, null, null, false));
      seq.add(new Request(null, "OPTIONS", "/b7", null, null, null, false));
      seq.add(new Request(null, "TRACE", "/b7", null, null, null, false));
      seq.add(new Request(null, "GET", "/b7", null, null, null, false));
      seq.add(new Request(null, "PUT", "/b7", null, null, null, false));

      if (!seq.isIdempotent(new Request(null, null, "/b1", null, null, null, false)))
         System.err.println("Sequence b1 failed");
      if (!seq.isIdempotent(new Request(null, null, "/b2", null, null, null, false)))
         System.err.println("Sequence b2 failed");
      if (!seq.isIdempotent(new Request(null, null, "/b3", null, null, null, false)))
         System.err.println("Sequence b3 failed");
      if (seq.isIdempotent(new Request(null, null, "/b4", null, null, null, false)))
         System.err.println("Sequence b4 failed");
      if (!seq.isIdempotent(new Request(null, null, "/b5", null, null, null, false)))
         System.err.println("Sequence b5 failed");
      if (seq.isIdempotent(new Request(null, null, "/b6", null, null, null, false)))
         System.err.println("Sequence b6 failed");
      if (seq.isIdempotent(new Request(null, null, "/b7", null, null, null, false)))
         System.err.println("Sequence b7 failed");
      if (seq.isIdempotent(new Request(null, null, "/b8", null, null, null, false)))
         System.err.println("Sequence b8 failed");
      if (seq.isIdempotent(new Request(null, null, "/b9", null, null, null, false)))
         System.err.println("Sequence b9 failed");

      System.out.println("Tests finished");
   }
*/
}
